/*-
 * Copyright (c) 2014 Shang-Rong Cai. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHORS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 * $ DIDF: did.c    Rev. 0.1.1    2014-06-09T17:17+08:00 $
 */

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdint.h>
#include <complex.h>
#include <errno.h>

#include <did.h>

#ifndef BUFFER_SIZE
#define BUFFER_SIZE 8
#endif

/* Locally Private Function */
int did_check_read_length(size_t read, size_t exact);

size_t write_preserving_byte(FILE *fpof, size_t cnt, uint8_t dummy);

int did_write_head(FILE *fpof, const did_head_t *hdprt);

int did_write_meta(FILE *fpof, const did_meta_t *mtprt);


int get_index_type_size(const uint8_t idxtyp, size_t *idx_sz);

int get_entry_type_size(const uint8_t enttyp, size_t *dat_sz);


int count_index(const uint8_t idxtyp, const uint64_t idx_lst_z, const void *idx_lst, const uint64_t cnt_lst_sz, uint64_t *cnt_lst);

int construct_distribution(const uint8_t idxtyp, const uint64_t sz, uint64_t *cnt_lst, void *dst_lst);


void swap_entry(void *val_a, void *val_b, size_t bkz);


void sort_index_data_int32(void *idx_dat_lst, size_t dat_sz, size_t st_l, size_t st_r);

void sort_index_data_int64(void *idx_dat_lst, size_t dat_sz, size_t st_l, size_t st_r);


void read_i32(FILE *fpif, uint64_t sz, int32_t *dst, void *idx, void *val, size_t val_bkz);

void read_i64(FILE *fpif, uint64_t sz, int64_t *dst, void *idx, void *val, size_t val_bkz);


int did_check_read_length(size_t read, size_t exact)
{
    int ierr = ERRNO_UNDEFINED;

#ifdef TRACE_INFO
    printf("[F] did_check_read_length()\n");
#endif

    if (read != exact)
    {
        printf("READ LENGTH TOO SHORT\n");
        ierr = ENOSYS;
    }

#ifdef TRACE_INFO
    printf("[ ] did_check_read_length()\n");
#endif

    return ierr;
}


int did_head_set_info(did_head_t *hdprt, uint8_t idxtyp, uint8_t enttyp)
{
    int ierr = ERRNO_UNDEFINED;

#ifdef TRACE_INFO
    printf("[F] did_head_set_info()\n");
#endif

    /* DID File Identify Code */
    memcpy(hdprt->identify, cntstr_did_idc, DID_HEAD_IDC_SIZE);

    /* Set Index Type */
    switch (idxtyp)
    {
        case DID_HEAD_INDEX_T_I32:
            hdprt->index_type = DID_HEAD_INDEX_T_I32;
            break;
        case DID_HEAD_INDEX_T_I64:
            hdprt->index_type = DID_HEAD_INDEX_T_I64;
            break;
        default:
            ierr = ERRNO_UNKNOWN_TYPE;
            goto EXIT_DID_HEAD_SET_INFO;
            break;
    }

    /* Set Data Entry Type */
    switch (enttyp)
    {
        case DID_HEAD_DATA_T_F32:
            hdprt->entry_type = DID_HEAD_DATA_T_F32;
            break;
        case DID_HEAD_DATA_T_F64:
            hdprt->entry_type = DID_HEAD_DATA_T_F64;
            break;
        case DID_HEAD_DATA_T_C32:
            hdprt->entry_type = DID_HEAD_DATA_T_C32;
            break;
        case DID_HEAD_DATA_T_C64:
            hdprt->entry_type = DID_HEAD_DATA_T_C64;
            break;
        case DID_HEAD_DATA_T_I32:
            hdprt->entry_type = DID_HEAD_DATA_T_I32;
            break;
        case DID_HEAD_DATA_T_I64:
            hdprt->entry_type = DID_HEAD_DATA_T_I64;
            break;
        default:
            ierr = ERRNO_UNKNOWN_TYPE;
            goto EXIT_DID_HEAD_SET_INFO;
            break;
    }

    /* Set Endianness */
    hdprt->endian_type = DID_HEAD_ENDIAN_LITTLE;

    /* Version Number Code */
    memcpy(hdprt->ver_num, cntstr_did_num, DID_HEAD_NUM_SIZE);

    /* Version Tag Code */
    memcpy(hdprt->ver_tag, cntstr_did_tag, DID_HEAD_TAG_SIZE);

    EXIT_DID_HEAD_SET_INFO:
#ifdef TRACE_INFO
    printf("[ ] did_head_set_info()\n");
#endif

    return ierr;
}


int did_head_stdout(const did_head_t *hdprt)
{
    int ierr = ERRNO_UNDEFINED;

#ifdef TRACE_INFO
    printf("[F] did_head_stdout()\n");
#endif

    printf("    Index Type: ");
    switch (hdprt->index_type)
    {
        case DID_HEAD_INDEX_T_I32:
            printf("Signed 32 Bits Integer\n");
            break;
        case DID_HEAD_INDEX_T_I64:
            printf("Signed 64 Bits Integer\n");
            break;
        default:
            ierr = ERRNO_UNKNOWN_TYPE;
            break;
    }

    printf("    Entry Type: ");
    switch (hdprt->entry_type)
    {
        case DID_HEAD_DATA_T_F32:
            printf("32 Bits Float-Point Number\n");
            break;
        case DID_HEAD_DATA_T_F64:
            printf("64 Bits Float-Point Number\n");;
            break;
        case DID_HEAD_DATA_T_C32:
            printf("Complex Number With 32 Bits Float-Point Number (64 Bits)\n");
            break;
        case DID_HEAD_DATA_T_C64:
            printf("Complex Number With 64 Bits Float-Point Number (128 Bits) \n");
            break;
        case DID_HEAD_DATA_T_I32:
            printf("Signed 32 Bits Integer\n");
            break;
        case DID_HEAD_DATA_T_I64:
            printf("Signed 64 Bits Integer\n");
            break;
        default:
            ierr = ERRNO_UNKNOWN_TYPE;
            break;
    }

    printf("    Endianness: ");
    switch(hdprt->endian_type)
    {
        case DID_HEAD_ENDIAN_LITTLE:
            printf("Little Endian\n");
            break;
        case DID_HEAD_ENDIAN_BIG:
            printf("Big Endian\n");
            break;
        default:
            ierr = ERRNO_ENDIAN;
            break;
    }

    printf("    Version Number: ");
    putchar((int) hdprt->ver_num[0]);
    putchar((int) hdprt->ver_num[1]);
    putchar((int) hdprt->ver_num[2]);
    putchar((int) '.');
    putchar((int) hdprt->ver_num[3]);
    putchar((int) hdprt->ver_num[4]);
    putchar((int) '.');
    putchar((int) hdprt->ver_num[5]);
    putchar((int) hdprt->ver_num[6]);
    putchar((int) hdprt->ver_num[7]);
    putchar((int) '\n');

    printf("    Version Tag: ");
    putchar((int) hdprt->ver_tag[0]);
    putchar((int) hdprt->ver_tag[1]);
    putchar((int) hdprt->ver_tag[2]);
    putchar((int) hdprt->ver_tag[3]);
    putchar((int) hdprt->ver_tag[4]);
    putchar((int) hdprt->ver_tag[5]);
    putchar((int) hdprt->ver_tag[6]);
    putchar((int) hdprt->ver_tag[7]);
    putchar((int) '\n');

#ifdef TRACE_INFO
    printf("[ ] did_head_stdout()\n");
#endif

    return ierr;
}


int did_meta_set_info(did_meta_t *mtprt, const did_head_t *hdprt, const uint64_t fiz, const uint64_t siz, const uint64_t dez)
{
    int ierr = ERRNO_UNDEFINED;

    size_t idx_sz;
    size_t dat_sz;

#ifdef TRACE_INFO
    printf("[F] did_meta_set_info()\n");
#endif

    /* Set Size By Index Type */
    ierr = get_index_type_size(hdprt->index_type, &idx_sz);

    if (ierr != ERRNO_UNDEFINED)
    {
        goto EXIT_DID_META_SET_INFO;
    }

    /* Set Size By Data Entry Type */
    ierr = get_entry_type_size(hdprt->entry_type, &dat_sz);

    if (ierr != ERRNO_UNDEFINED)
    {
        goto EXIT_DID_META_SET_INFO;
    }

    /* Set Size */
    mtprt->fst_idx_sz = fiz;
    mtprt->snd_idx_sz = siz;
    mtprt->dat_ent_sz = dez;

    /* Set Address */
    mtprt->fst_idx_dst_addr = DID_ADDR_OFFSET_BODY;
    mtprt->idx_dat_lst_addr = mtprt->fst_idx_dst_addr + idx_sz * (fiz + 1);

    mtprt->snd_idx_dst_addr = mtprt->idx_dat_lst_addr + (idx_sz + dat_sz) * dez;
    mtprt->idx_shf_lst_addr = mtprt->snd_idx_dst_addr + idx_sz * (siz + 1);

    EXIT_DID_META_SET_INFO:
#ifdef TRACE_INFO
    printf("[ ] did_meta_set_info()\n");
#endif

    return ierr;
}


int did_meta_stdout(const did_meta_t *mtprt)
{
    int ierr = ERRNO_UNDEFINED;

#ifdef TRACE_INFO
    printf("[F] did_meta_stdout()\n");
#endif

    printf("Size Information:\n");
    printf("    Least upper bound of first index: %ld\n", mtprt->fst_idx_sz);
    printf("    Least upper bound of second index: %ld\n", mtprt->snd_idx_sz);
    printf("    Number of data entries: %ld\n", mtprt->dat_ent_sz);

    printf("Relative Address:\n");
    printf("    Distribution by first index: %ld\n", mtprt->fst_idx_dst_addr);
    printf("    Indexed data entry: %ld\n", mtprt->idx_dat_lst_addr);
    printf("    Distribution by second index: %ld\n", mtprt->snd_idx_dst_addr);
    printf("    Index and offset: %ld\n", mtprt->idx_shf_lst_addr);

#ifdef TRACE_INFO
    printf("[ ] did_meta_stdout()\n");
#endif

    return ierr;
}


int did_read_head(FILE *fpif, did_head_t *hdprt)
{
    size_t itmz;

    uint8_t buffer[BUFFER_SIZE];

#ifdef TRACE_INFO
    printf("[F] did_read_head()\n");
#endif

    fseek(fpif, DID_ADDR_OFFSET_HEAD, SEEK_SET);

    /* File Identify */
    itmz = fread((void*) hdprt->identify, sizeof(uint8_t), DID_HEAD_IDC_SIZE, fpif);

    /* Preserving Part 0 */
    itmz += fread((void*) buffer, sizeof(uint8_t), BUFFER_SIZE, fpif);

    /* Number Of Bytes And Data Element Type */
    itmz += fread((void*) &hdprt->index_type, sizeof(uint8_t), 1, fpif);
    itmz += fread((void*) &hdprt->entry_type, sizeof(uint8_t), 1, fpif);

    /* Preserving Part 1 */
    itmz += fread((void*) buffer, sizeof(uint8_t), 6, fpif);

    /* Endianness */
    itmz += fread((void*) &hdprt->endian_type, sizeof(uint64_t), 1, fpif);

    /* Version Number And Text */
    itmz += fread((void*) &hdprt->ver_num, sizeof(uint8_t), DID_HEAD_NUM_SIZE, fpif);
    itmz += fread((void*) &hdprt->ver_tag, sizeof(uint8_t), DID_HEAD_TAG_SIZE, fpif);

    /* Preserving Part 2 */

#ifdef DEBUG_INFO
    printf("read length %zd\n", itmz);
#endif

#ifdef TRACE_INFO
    printf("[ ] did_read_head()\n");
#endif

    return errno;
}


int did_read_meta(FILE *fpif, did_meta_t *mtprt)
{
    size_t itmz;

#ifdef TRACE_INFO
    printf("[F] did_read_meta()\n");
#endif

    fseek(fpif, DID_ADDR_OFFSET_META, SEEK_SET);

    /* First Index Least Upper Bound */
    itmz = fread((void*) &mtprt->fst_idx_sz, sizeof(uint64_t), 1, fpif);

    /* Second Index Least Upper Bound */
    itmz += fread((void*) &mtprt->snd_idx_sz, sizeof(uint64_t), 1, fpif);

    /* Number of Data Entries */
    itmz += fread((void*) &mtprt->dat_ent_sz, sizeof(uint64_t), 1, fpif);

    /* Address for first index depended distribution */
    itmz += fread((void*) &mtprt->fst_idx_dst_addr, sizeof(uint64_t), 1, fpif);

    /* Address for indexed data entry list */
    itmz += fread((void*) &mtprt->idx_dat_lst_addr, sizeof(uint64_t), 1, fpif);

    /* Address for second index depended distribution */
    itmz += fread((void*) &mtprt->snd_idx_dst_addr, sizeof(uint64_t), 1, fpif);

    /* Address for index and offset list */
    itmz += fread((void*) &mtprt->idx_shf_lst_addr, sizeof(uint64_t), 1, fpif);

#ifdef DEBUG_INFO
    printf("read length %zd\n", itmz);
#endif

#ifdef TRACE_INFO
    printf("[ ] did_read_meta()\n");
#endif

    return errno;
}


size_t write_preserving_byte(FILE *fpof, size_t cnt, uint8_t dummy)
{
    size_t zi;
    size_t length;

#ifdef TRACE_INFO
    printf("[F] size_t write_preserving_byte()\n");
#endif

    length = 0;

    for (zi = 0; zi < cnt; zi++)
    {
        length += fwrite((void*) &dummy, sizeof(uint8_t), 1, fpof);
    }

#ifdef TRACE_INFO
    printf("[F] size_t write_preserving_byte()\n");
#endif

    return length;
}


int did_write_head(FILE *fpof, const did_head_t *hdprt)
{
    size_t itmz;

#ifdef TRACE_INFO
    printf("[F] did_write_head()\n");
#endif

    fseek(fpof, DID_ADDR_OFFSET_HEAD, SEEK_SET);

    /* File Identify */
    itmz = fwrite((void*) hdprt->identify, sizeof(uint8_t), DID_HEAD_IDC_SIZE, fpof);

    /* Preserving Part 0 */
    itmz += write_preserving_byte(fpof, 8, 0x00);

    /* Number Of Bytes And Data Element Type */
    itmz += fwrite((void*) &hdprt->index_type, sizeof(uint8_t), 1, fpof);
    itmz += fwrite((void*) &hdprt->entry_type, sizeof(uint8_t), 1, fpof);

    /* Preserving Part 1 */
    itmz += write_preserving_byte(fpof, 6, 0x01);

    /* Endianness */
    itmz += fwrite((void*) &hdprt->endian_type, sizeof(uint64_t), 1, fpof);

    /* Version Number And Text */
    itmz += fwrite((void*) &hdprt->ver_num, sizeof(uint8_t), DID_HEAD_NUM_SIZE, fpof);
    itmz += fwrite((void*) &hdprt->ver_tag, sizeof(uint8_t), DID_HEAD_TAG_SIZE, fpof);

    /* Preserving Part 2 */
    itmz += write_preserving_byte(fpof, 16, 0x02);

#ifdef DEBUG_INFO
    printf("write length %zd\n", itmz);
#endif

#ifdef TRACE_INFO
    printf("[ ] did_write_head()\n");
#endif

    return errno;
}


int did_write_meta(FILE *fpof, const did_meta_t *mtprt)
{
    size_t itmz;

#ifdef TRACE_INFO
    printf("[F] did_write_meta()\n");
#endif

    fseek(fpof, DID_ADDR_OFFSET_META, SEEK_SET);

    /* Write Amount Part */
    itmz = fwrite((void*) &mtprt->fst_idx_sz, sizeof(uint64_t), 1, fpof);
    itmz += fwrite((void*) &mtprt->snd_idx_sz, sizeof(uint64_t), 1, fpof);
    itmz += fwrite((void*) &mtprt->dat_ent_sz, sizeof(uint64_t), 1, fpof);

    /* Offset Part For First Index Style */
    itmz += fwrite((void*) &mtprt->fst_idx_dst_addr, sizeof(uint64_t), 1, fpof);
    itmz += fwrite((void*) &mtprt->idx_dat_lst_addr, sizeof(uint64_t), 1, fpof);

    /* Offset Part For Second Index Style */
    itmz += fwrite((void*) &mtprt->snd_idx_dst_addr, sizeof(uint64_t), 1, fpof);
    itmz += fwrite((void*) &mtprt->idx_shf_lst_addr, sizeof(uint64_t), 1, fpof);

    /* Preserving Part */
    itmz += write_preserving_byte(fpof, 8, 0x00);

#ifdef DEBUG_INFO
    printf("write length %zd\n", itmz);
#endif

#ifdef TRACE_INFO
    printf("[ ] did_write_meta()\n");
#endif

    return errno;
}


int count_index(const uint8_t idxtyp, const uint64_t idx_lst_sz, const void *idx_lst, const uint64_t cnt_lst_sz, uint64_t *cnt_lst)
{
    int ierr = ERRNO_UNDEFINED;
    uint64_t ui;

    int32_t *ptr_idx_32;
    int64_t *ptr_idx_64;

#ifdef TRACE_INFO
    printf("[F] count_index()\n");
#endif

    ptr_idx_32 = (int32_t*) idx_lst;
    ptr_idx_64 = (int64_t*) idx_lst;

    /* Reset Counter */
    for (ui = 0; ui < cnt_lst_sz; ui++)
    {
        cnt_lst[ui] = 0;
    }

    /* Counting */
    switch (idxtyp)
    {
        case DID_HEAD_INDEX_T_I32:
            for (ui = 0; ui < idx_lst_sz; ui++)
            {
                cnt_lst[ptr_idx_32[ui]]++;
            }
            break;
        case DID_HEAD_INDEX_T_I64:
            for (ui = 0; ui < idx_lst_sz; ui++)
            {
                cnt_lst[ptr_idx_64[ui]]++;
            }
            break;
        default:
            ierr = ERRNO_UNKNOWN_TYPE;
            break;
    }

#ifdef TRACE_INFO
    printf("[ ] count_index()\n");
#endif

    return ierr;
}


int construct_distribution(const uint8_t idxtyp, const uint64_t sz, uint64_t *cnt_lst, void *dst_lst)
{
    int ierr = ERRNO_UNDEFINED;

    uint64_t ui;

    int32_t *ptr_idx_32;
    int64_t *ptr_idx_64;

#ifdef TRACE_INFO
    printf("[F] construct_distribution()\n");
#endif

    ptr_idx_32 = (int32_t*) dst_lst;
    ptr_idx_64 = (int64_t*) dst_lst;

    /* Construct Distribution */
    switch (idxtyp)
    {
        case DID_HEAD_INDEX_T_I32:
            ptr_idx_32[0] = 0;
            for (ui = 0; ui < sz; ui++)
            {
                ptr_idx_32[ui + 1] = ptr_idx_32[ui] + (int32_t) cnt_lst[ui];
            }
            break;
        case DID_HEAD_INDEX_T_I64:
            ptr_idx_64[0] = 0;
            for (ui = 0; ui < sz; ui++)
            {
                ptr_idx_64[ui + 1] = ptr_idx_64[ui] + (int64_t) cnt_lst[ui];
            }
            break;
        default:
            ierr = ERRNO_UNKNOWN_TYPE;
            break;
    }

#ifdef TRACE_INFO
    printf("[ ] construct_distribution()\n");
#endif

    return ierr;
}


int did_body_create(did_body_t *bdprt, const did_head_t *hdprt, const did_meta_t *mtprt, const void *fst_idx_lst, const void *snd_idx_lst, const void* dat_ent_lst)
{
    int ierr = ERRNO_UNDEFINED;

    size_t zi;

    size_t idx_sz;
    size_t dat_sz;
    size_t blk_sz;

    size_t cnt_sz;  /* For maximum counter for index */
    uint64_t *cnt_idx_dst;  /* Count non-zero for index of each distribution */

    int32_t *ptr_dst_32;
    int64_t *ptr_dst_64;

    int32_t *ptr_idx_32;
    int64_t *ptr_idx_64;

    ssize_t cur_idx;
    ssize_t cur_pos;

    int32_t i32i, dst_head_32, dst_tail_32;  /* int32_t based loop counter or index, loop head, tail */
    int64_t i64i, dst_head_64, dst_tail_64;  /* int64_t based loop counter or index, loop head, tail */

    int32_t tmp_cur_idx_32;
    int64_t tmp_cur_idx_64;

#ifdef TRACE_INFO
    printf("[F] did_body_create()\n");
#endif

    /* Set Size By Index Type */
    ierr = get_index_type_size(hdprt->index_type, &idx_sz);

    if (ierr != ERRNO_UNDEFINED)
    {
        goto EXIT_DID_BODY_CREATE;
    }

    /* Set Size By Data Entry Type */
    ierr = get_entry_type_size(hdprt->entry_type, &dat_sz);

    if (ierr != ERRNO_UNDEFINED)
    {
        goto EXIT_DID_BODY_CREATE;
    }

    blk_sz = idx_sz + dat_sz;

    /* Allocate Memory For Data */
    bdprt->fst_dst = calloc((size_t) mtprt->fst_idx_sz + 1, idx_sz);
    bdprt->ide_lst = calloc((size_t) mtprt->dat_ent_sz, blk_sz);

    bdprt->snd_dst = calloc((size_t) mtprt->snd_idx_sz + 1, idx_sz);
    bdprt->iao_lst = calloc((size_t) mtprt->dat_ent_sz, idx_sz * 2);

    /* Allocate Memory For Counter */
    if (mtprt->fst_idx_sz < mtprt->snd_idx_sz)
    {
        cnt_sz = (size_t) mtprt->snd_idx_sz;
    }
    else
    {
        cnt_sz = (size_t) mtprt->fst_idx_sz;
    }

    cnt_idx_dst = (uint64_t*) calloc(cnt_sz, sizeof(uint64_t));

    /* Count First Index */
    ierr = count_index(hdprt->index_type, mtprt->dat_ent_sz, fst_idx_lst, mtprt->fst_idx_sz, cnt_idx_dst);

    /* Construct Distribution Of Second Index And Data Entry */
    ierr = construct_distribution(hdprt->index_type, mtprt->fst_idx_sz, cnt_idx_dst, bdprt->fst_dst);

    /* Copy Second Index And Data Entry */
    ptr_dst_32 = (int32_t*) bdprt->fst_dst;
    ptr_dst_64 = (int64_t*) bdprt->fst_dst;

    ptr_idx_32 = (int32_t*) fst_idx_lst;
    ptr_idx_64 = (int64_t*) fst_idx_lst;

    for (zi = 0; zi < (size_t) mtprt->fst_idx_sz; zi++)
    {
        cnt_idx_dst[zi] = 0;
    }

    switch (hdprt->index_type)
    {
        case DID_HEAD_INDEX_T_I32:
            for (zi = 0; zi < (size_t) mtprt->dat_ent_sz; zi++)
            {
                cur_idx = ptr_idx_32[zi];
                cur_pos = ptr_dst_32[cur_idx] + (size_t) cnt_idx_dst[cur_idx];

                memcpy(bdprt->ide_lst + cur_pos * blk_sz, snd_idx_lst + zi * idx_sz, idx_sz);
                memcpy(bdprt->ide_lst + cur_pos * blk_sz + idx_sz, dat_ent_lst + zi * dat_sz, dat_sz);

                cnt_idx_dst[cur_idx]++;
            }
            break;
        case DID_HEAD_INDEX_T_I64:
            for (zi = 0; zi < (size_t) mtprt->dat_ent_sz; zi++)
            {
                cur_idx = ptr_idx_64[zi];
                cur_pos = ptr_dst_64[cur_idx] + (size_t) cnt_idx_dst[cur_idx];

                memcpy(bdprt->ide_lst + cur_pos * blk_sz, snd_idx_lst + zi * idx_sz, idx_sz);
                memcpy(bdprt->ide_lst + cur_pos * blk_sz + idx_sz, dat_ent_lst + zi * dat_sz, dat_sz);

                cnt_idx_dst[cur_idx]++;
            }
            break;
        default:
            ierr = ERRNO_UNKNOWN_TYPE;
            break;
    }

    /* Sort Second Index */
    switch (hdprt->index_type)
    {
        case DID_HEAD_INDEX_T_I32:
            for (zi = 0; zi < (size_t) mtprt->fst_idx_sz; zi++)
            {
                memcpy((void*) &dst_head_32, bdprt->fst_dst + zi * idx_sz, idx_sz);
                memcpy((void*) &dst_tail_32, bdprt->fst_dst + (zi + 1) * idx_sz, idx_sz);

                sort_index_data_int32(bdprt->ide_lst, dat_sz, (size_t) dst_head_32, (size_t) dst_tail_32);
            }
            break;
        case DID_HEAD_INDEX_T_I64:
            for (zi = 0; zi < (size_t) mtprt->fst_idx_sz; zi++)
            {
                memcpy((void*) &dst_head_64, bdprt->fst_dst + zi * idx_sz, idx_sz);
                memcpy((void*) &dst_tail_64, bdprt->fst_dst + (zi + 1) * idx_sz, idx_sz);

                sort_index_data_int64(bdprt->ide_lst, dat_sz, (size_t) dst_head_64, (size_t) dst_head_64);
            }
            break;
        default:
            ierr = ERRNO_UNKNOWN_TYPE;
            break;
    }

    /* Count Second Index */
    ierr = count_index(hdprt->index_type, mtprt->dat_ent_sz, snd_idx_lst, mtprt->snd_idx_sz, cnt_idx_dst);

    /* Construct Distribution Of First Index And Data Entry */
    ierr = construct_distribution(hdprt->index_type, mtprt->snd_idx_sz, cnt_idx_dst, bdprt->snd_dst);

    /* Copy First Index And Data Position Offset */
    ptr_dst_32 = (int32_t*) bdprt->fst_dst;
    ptr_dst_64 = (int64_t*) bdprt->fst_dst;

    for (zi = 0; zi < (size_t) mtprt->fst_idx_sz; zi++)
    {
        cnt_idx_dst[zi] = 0;
    }

    switch (hdprt->index_type)
    {
        case DID_HEAD_INDEX_T_I32:
            for (zi = 0; zi < (size_t) mtprt->fst_idx_sz; zi++)
            {
                memcpy((void*) &dst_head_32, bdprt->fst_dst + zi * idx_sz, idx_sz);
                memcpy((void*) &dst_tail_32, bdprt->fst_dst + (zi + 1) * idx_sz, idx_sz);

                for (i32i = dst_head_32; i32i < dst_tail_32; i32i++)
                {
                    memcpy((void*) &cur_idx, bdprt->ide_lst + i32i * blk_sz, idx_sz);
                    memcpy((void*) &cur_pos, bdprt->snd_dst + cur_idx * idx_sz, idx_sz);
                    cur_pos += cnt_idx_dst[cur_idx];

                    tmp_cur_idx_32 = (int32_t) zi;
                    memcpy(bdprt->iao_lst + cur_pos * idx_sz * 2, (void*) &tmp_cur_idx_32, idx_sz);

                    tmp_cur_idx_32 = (int32_t) (i32i - dst_head_32);
                    memcpy(bdprt->iao_lst + cur_pos * idx_sz * 2 + idx_sz, (void*) &tmp_cur_idx_32, idx_sz);

                    cnt_idx_dst[cur_idx]++;
                }
            }
            break;
        case DID_HEAD_INDEX_T_I64:
            for (zi = 0; zi < (size_t) mtprt->fst_idx_sz; zi++)
            {
                memcpy((void*) &dst_head_64, bdprt->fst_dst + zi * idx_sz, idx_sz);
                memcpy((void*) &dst_tail_64, bdprt->fst_dst + (zi + 1) * idx_sz, idx_sz);

                for (i64i = dst_head_64; i64i < dst_tail_64; i64i++)
                {
                    memcpy((void*) &cur_idx, bdprt->ide_lst + i64i * blk_sz, idx_sz);
                    memcpy((void*) &cur_pos, bdprt->snd_dst + cur_idx * idx_sz, idx_sz);
                    cur_pos += cnt_idx_dst[cur_idx];

                    tmp_cur_idx_64 = (int64_t) zi;
                    memcpy(bdprt->iao_lst + cur_pos * idx_sz * 2, (void*) &tmp_cur_idx_64, idx_sz);

                    tmp_cur_idx_64 = (int64_t) (i64i - dst_head_64);
                    memcpy(bdprt->iao_lst + cur_pos * idx_sz * 2 + idx_sz, (void*) &tmp_cur_idx_64, idx_sz);

                    cnt_idx_dst[cur_idx]++;
                }
            }
            break;
        default:
            ierr = ERRNO_UNKNOWN_TYPE;
            break;
    }

    free(cnt_idx_dst);

    EXIT_DID_BODY_CREATE:
#ifdef TRACE_INFO
    printf("[ ] did_body_create()\n");
#endif

    return ierr;
}


int did_body_delete(did_body_t *bdprt)
{
    int ierr = ERRNO_UNDEFINED;

#ifdef TRACE_INFO
    printf("[F] did_body_delete()\n");
#endif

    free(bdprt->fst_dst);
    free(bdprt->ide_lst);

    free(bdprt->snd_dst);
    free(bdprt->iao_lst);

#ifdef TRACE_INFO
    printf("[ ] did_body_delete()\n");
#endif

    return ierr;
}


int did_read_body(FILE *fpif, did_head_t *hdprt, did_meta_t *mtprt, did_body_t *bdprt)
{
    int ierr = ERRNO_UNDEFINED;

    size_t itmz;

    size_t idx_sz;
    size_t dat_sz;

#ifdef TRACE_INFO
    printf("[F] did_read_body()\n");
#endif

    /* Set Size By Index Type */
    ierr = get_index_type_size(hdprt->index_type, &idx_sz);

    if (ierr != ERRNO_UNDEFINED)
    {
        goto EXIT_DID_READ_BODY;
    }

    /* Set Size By Data Entry Type */
    ierr = get_entry_type_size(hdprt->entry_type, &dat_sz);

    if (ierr != ERRNO_UNDEFINED)
    {
        goto EXIT_DID_READ_BODY;
    }

    fseek(fpif, DID_ADDR_OFFSET_BODY, SEEK_SET);

    /* Distribution depended on first index */
    itmz = fread(bdprt->fst_dst, idx_sz, (size_t) mtprt->fst_idx_sz + 1, fpif);

    /* Indexed Data Entries */
    itmz += fread(bdprt->ide_lst, idx_sz + dat_sz, (size_t) mtprt->dat_ent_sz, fpif);

    /* Distribution depended on second index */
    itmz += fread(bdprt->snd_dst, idx_sz, (size_t) mtprt->snd_idx_sz + 1, fpif);

    /* Index And Offset */
    itmz += fread(bdprt->iao_lst, idx_sz * 2, (size_t) mtprt->dat_ent_sz, fpif);

#ifdef DEBUG_INFO
    printf("read length %zd\n", itmz);
#endif

    EXIT_DID_READ_BODY:
#ifdef TRACE_INFO
    printf("[ ] did_read_body()\n");
#endif

    return ierr;
}


int did_read_body_fiwise(FILE *fpif, void *dst, void *idx, void *val)
{
    int ierr = ERRNO_UNDEFINED;

    did_head_t hdprt;
    did_meta_t mtprt;

    size_t idx_sz;
    size_t dat_sz;

#ifdef TRACE_INFO
    printf("[F] did_read_body_fiwise()\n");
#endif

    /* Read Head Part And Meta Part */
    ierr = did_read_head(fpif, &hdprt);
    ierr = did_read_meta(fpif, &mtprt);

    /* Set Size By Index Type */
    ierr = get_index_type_size(hdprt.index_type, &idx_sz);

    if (ierr != ERRNO_UNDEFINED)
    {
        goto EXIT_DID_READ_BODY_FIWISE;
    }

    /* Set Size By Data Entry Type */
    ierr = get_entry_type_size(hdprt.entry_type, &dat_sz);

    if (ierr != ERRNO_UNDEFINED)
    {
        goto EXIT_DID_READ_BODY_FIWISE;
    }

    fseek(fpif, DID_ADDR_OFFSET_BODY, SEEK_SET);

    /* Second indices distribution depended on first index */
    fread(dst, idx_sz, (size_t) mtprt.fst_idx_sz + 1, fpif);

    switch (hdprt.index_type)
    {
        case DID_HEAD_INDEX_T_I32:
            read_i32(fpif, mtprt.fst_idx_sz, dst, idx, val, dat_sz);
            break;
        case DID_HEAD_INDEX_T_I64:
            read_i64(fpif, mtprt.fst_idx_sz, dst, idx, val, dat_sz);
            break;
    }

    EXIT_DID_READ_BODY_FIWISE:
#ifdef TRACE_INFO
    printf("[F] did_read_body_fiwise()\n");
#endif

    return ierr;
}


int did_write(FILE *fpof, const did_head_t *hdprt, const did_meta_t *mtprt, const did_body_t *bdprt)
{
    int ierr;
    size_t itmz;

    size_t idx_sz;
    size_t dat_sz;

#ifdef TRACE_INFO
    printf("[F] did_write()\n");
#endif

    ierr = did_write_head(fpof, hdprt);
    ierr = did_write_meta(fpof, mtprt);

    fseek(fpof, DID_ADDR_OFFSET_BODY, SEEK_SET);

    /* Set Size By Index Type */
    ierr = get_index_type_size(hdprt->index_type, &idx_sz);

    /* Set Size By Data Entry Type */
    ierr = get_entry_type_size(hdprt->entry_type, &dat_sz);

    /* Distribution depended on first index */
    itmz = fwrite(bdprt->fst_dst, idx_sz, (size_t) mtprt->fst_idx_sz + 1, fpof);

    /* Indexed Data Entries */
    itmz += fwrite(bdprt->ide_lst, idx_sz + dat_sz, (size_t) mtprt->dat_ent_sz, fpof);

    /* Distribution depended on second index */
    itmz += fwrite(bdprt->snd_dst, idx_sz, (size_t) mtprt->snd_idx_sz + 1, fpof);

    /* Index And Offset */
    itmz += fwrite(bdprt->iao_lst, idx_sz * 2, (size_t) mtprt->dat_ent_sz, fpof);

#ifdef DEBUG_INFO
    printf("write length %zd\n", itmz);
#endif

#ifdef TRACE_INFO
    printf("[ ] did_write()\n");
#endif

    return ierr;
}


/* Get Size By Index Type */
int get_index_type_size(const uint8_t idxtyp, size_t *idx_sz)
{
    int ierr = ERRNO_UNDEFINED;

#ifdef TRACE_INFO
   printf("[F] get_index_type_size()\n");
#endif

    switch (idxtyp)
    {
        case DID_HEAD_INDEX_T_I32:
            *idx_sz = sizeof(int32_t);
            break;
        case DID_HEAD_INDEX_T_I64:
            *idx_sz = sizeof(int64_t);
            break;
        default:
            *idx_sz = 0;
            ierr = ERRNO_UNKNOWN_TYPE;
            break;
    }

#ifdef TRACE_INFO
   printf("[ ] get_index_type_size()\n");
#endif

    return ierr;
}


/* Get Size By Data Entry Type */
int get_entry_type_size(const uint8_t enttyp, size_t *dat_sz)
{
    int ierr = ERRNO_UNDEFINED;

#ifdef TRACE_INFO
   printf("[F] get_entry_type_size()\n");
#endif

    switch (enttyp)
    {
        case DID_HEAD_DATA_T_F32:
            *dat_sz = sizeof(float);
            break;
        case DID_HEAD_DATA_T_F64:
            *dat_sz = sizeof(double);
            break;
        case DID_HEAD_DATA_T_C32:
            *dat_sz = sizeof(float complex);
            break;
        case DID_HEAD_DATA_T_C64:
            *dat_sz = sizeof(double complex);
            break;
        case DID_HEAD_DATA_T_I32:
            *dat_sz = sizeof(int32_t);
            break;
        case DID_HEAD_DATA_T_I64:
            *dat_sz = sizeof(int64_t);
            break;
        default:
            *dat_sz = 0;
            ierr = ERRNO_UNKNOWN_TYPE;
            break;
    }

#ifdef TRACE_INFO
   printf("[ ] get_entry_type_size()\n");
#endif

    return ierr;
}


void swap_entry(void *val_a, void *val_b, size_t bkz)
{
    size_t zi;

    uint8_t buf_val;

    uint8_t *ptr_a;
    uint8_t *ptr_b;

#ifdef TRACE_INFO
    printf("[F] swap_entry()\n");
#endif

    ptr_a = (uint8_t*) val_a;
    ptr_b = (uint8_t*) val_b;

    for (zi = 0; zi < bkz; zi++)
    {
        buf_val = ptr_a[zi];
        ptr_a[zi] = ptr_b[zi];
        ptr_b[zi] = buf_val;
    }

#ifdef TRACE_INFO
    printf("[ ] swap_entry()\n");
#endif
}


void sort_index_data_int32(void *idx_dat_lst, size_t dat_sz, size_t st_l, size_t st_r)
{
    size_t zi, zj;
    size_t zt;  /* Break address */

    size_t idx_sz;
    size_t blk_sz;

    int32_t test_idx;
    int32_t test_try;

    size_t lstz;

#ifdef TRACE_INFO
    printf("[F] sort_index_data_int32()\n");
#endif

    idx_sz = sizeof(int32_t);
    blk_sz = idx_sz + dat_sz;

    lstz = st_r - st_l;

    if (lstz > 2)
    {
        memcpy((void*) &test_idx, idx_dat_lst + st_l * blk_sz, idx_sz);

        zi = st_l + 1;
        zj = st_r - 1;

        do
        {
            memcpy((void*) &test_try, idx_dat_lst + zi * blk_sz, idx_sz);

            while (zi < zj && test_try < test_idx)
            {
                zi++;
                memcpy((void*) &test_try, idx_dat_lst + zi * blk_sz, idx_sz);
            }

            memcpy((void*) &test_try, idx_dat_lst + zj * blk_sz, idx_sz);

            while (zi < zj && test_idx < test_try)
            {
                zj--;
                memcpy((void*) &test_try, idx_dat_lst + zj * blk_sz, idx_sz);
            }

            swap_entry(idx_dat_lst + zi * blk_sz, idx_dat_lst + zj * blk_sz, blk_sz);

            zt = zi;

            zi++;
            zj--;
        } while (zi < zj);

        memcpy((void*) &test_try, idx_dat_lst + zt * blk_sz, idx_sz);

        if (test_idx > test_try)
        {
            swap_entry(idx_dat_lst + st_l * blk_sz, idx_dat_lst + zt * blk_sz, blk_sz);
        }

        sort_index_data_int32(idx_dat_lst, dat_sz, st_l, zt);
        sort_index_data_int32(idx_dat_lst, dat_sz, zt, st_r);
    }
    else if (lstz == 2)
    {
        memcpy((void*) &test_idx, idx_dat_lst + st_l * blk_sz, idx_sz);
        memcpy((void*) &test_try, idx_dat_lst + (st_l + 1) * blk_sz, idx_sz);

        if (test_idx > test_try)
        {
            swap_entry(idx_dat_lst + st_l * blk_sz, idx_dat_lst + (st_l + 1) * blk_sz, blk_sz);
        }
    }

#ifdef TRACE_INFO
    printf("[ ] sort_index_data_int32()\n");
#endif
}


void sort_index_data_int64(void *idx_dat_lst, size_t dat_sz, size_t st_l, size_t st_r)
{
    size_t zi, zj;
    size_t zt;  /* Break address */

    size_t idx_sz;
    size_t blk_sz;

    int64_t test_idx;
    int64_t test_try;

    size_t lstz;

#ifdef TRACE_INFO
    printf("[F] sort_index_data_int64()\n");
#endif

    idx_sz = sizeof(int64_t);
    blk_sz = idx_sz + dat_sz;

    lstz = st_r - st_l;

    if (lstz > 2)
    {
        memcpy((void*) &test_idx, idx_dat_lst + st_l * blk_sz, idx_sz);

        zi = st_l + 1;
        zj = st_r - 1;

        do
        {
            memcpy((void*) &test_try, idx_dat_lst + zi * blk_sz, idx_sz);

            while (zi < zj && test_try < test_idx)
            {
                zi++;
                memcpy((void*) &test_try, idx_dat_lst + zi * blk_sz, idx_sz);
            }

            memcpy((void*) &test_try, idx_dat_lst + zj * blk_sz, idx_sz);

            while (zi < zj && test_idx < test_try)
            {
                zj--;
                memcpy((void*) &test_try, idx_dat_lst + zj * blk_sz, idx_sz);
            }

            swap_entry(idx_dat_lst + zi * blk_sz, idx_dat_lst + zj * blk_sz, blk_sz);

            zt = zi;

            zi++;
            zj--;
        } while (zi < zj);

        memcpy((void*) &test_try, idx_dat_lst + zt * blk_sz, idx_sz);

        if (test_idx > test_try)
        {
            swap_entry(idx_dat_lst + st_l * blk_sz, idx_dat_lst + zt * blk_sz, blk_sz);
        }

        sort_index_data_int64(idx_dat_lst, dat_sz, st_l, zt);
        sort_index_data_int64(idx_dat_lst, dat_sz, zt, st_r);
    }
    else if (lstz == 2)
    {
        memcpy((void*) &test_idx, idx_dat_lst + st_l * blk_sz, idx_sz);
        memcpy((void*) &test_try, idx_dat_lst + (st_l + 1) * blk_sz, idx_sz);

        if (test_idx > test_try)
        {
            swap_entry(idx_dat_lst + st_l * blk_sz, idx_dat_lst + (st_l + 1) * blk_sz, blk_sz);
        }
    }

#ifdef TRACE_INFO
    printf("[ ] sort_index_data_int64()\n");
#endif
}


void read_i32(FILE *fpif, uint64_t sz, int32_t *dst, void *idx, void *val, size_t val_bkz)
{
    uint64_t ui, uj;

    void *pidx;
    void *pval;

#ifdef TRACE_INFO
    printf("[F] read_i32()\n");
#endif

    pidx = idx;
    pval = val;

    for (ui = 0; ui < sz; ui++)
    {
        for (uj = dst[ui]; uj < dst[ui + 1]; uj++)
        {
            fread(pidx, sizeof(int32_t), 1, fpif);
            fread(pval, val_bkz, 1, fpif);

            pidx += sizeof(int32_t);
            pval += val_bkz;
        }
    }

#ifdef TRACE_INFO
    printf("[ ] read_i32()\n");
#endif
}


void read_i64(FILE *fpif, uint64_t sz, int64_t *dst, void *idx, void *val, size_t val_bkz)
{
    uint64_t ui, uj;

    void *pidx;
    void *pval;

#ifdef TRACE_INFO
    printf("[F] read_i64()\n");
#endif

    pidx = idx;
    pval = val;

    for (ui = 0; ui < sz; ui++)
    {
        for (uj = dst[ui]; uj < dst[ui + 1]; uj++)
        {
            fread(pidx, sizeof(int64_t), 1, fpif);
            fread(pval, val_bkz, 1, fpif);

            pidx += sizeof(int64_t);
            pval += val_bkz;
        }
    }

#ifdef TRACE_INFO
    printf("[ ] read_i64()\n");
#endif
}
